package com.celan.year2023.month06.day22;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Celan
 * @description TODO
 */
public class Solution {

    int[][] land;
    int m, n;

    public int[] pondSizes(int[][] land) {
        this.land = land;
        m = land.length;
        n = land[0].length;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 0) res.add(bfs(i, j));
            }
        }
        return res.stream().sorted().mapToInt(Integer::valueOf).toArray();
    }

    private int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        int cnt = 0;
        //将该点标记
        land[x][y] = -1;

        while (!queue.isEmpty()) {
            cnt++;
            int[] poll = queue.poll();
            int row = poll[0], col = poll[1];
            //将四周的水域加入队列
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i == 0 && j == 0) continue;
                    x = row + i;
                    y = col + j;
                    if (x >= 0 && y >= 0 && x < m & y < n && land[x][y] == 0) {
                        land[x][y] = -1;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ints = solution.pondSizes(new int[][]{
                {0, 2, 1, 0},
                {0, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 1, 0, 1}
        });
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

}
